/**
 * Version 1.
 * Stream   = String
 * Reason   = None
 * Result   = Pair<A, String>?
 */


/*
package parcomb
import java.util.ArrayList

// basic parsers

fun single<A>(result: A, str: String) = Pair<A, String>(result, str)

fun empty() = null

fun result<A>(r: A): (String) -> Pair<A, String>? = {(s: String) -> single<A>(r, s) }
fun zero() = {(s: String) -> empty() }
fun item() = {(s: String) -> if (s == "") null else single<Char>(s[0], s.substring(1)) }
fun itemnc() = {(s: String) -> if (s == "") null else single<Char>(s[0], s) }

// main combinators

fun bind<A, B>(p: (String) -> Pair<A, String>?,
               f: (A) -> ((String) -> Pair<B, String>?)): (String) -> Pair<B, String>? = {(s: String) ->
    val ans = p(s)
    if (ans == null)
        null
    else
        f(ans.first)(ans.second)
}

fun seq<A, B>(p: (String) -> Pair<A, String>?,
              q: (String) -> Pair<B, String>?): (String) -> Pair<Pair<A, B>, String>? = bind<A, Pair<A, B>>(
        p,
        {(x: A) ->
            bind<B, Pair<A, B>>(
                    q,
                    {(y: B) ->
                        result(Pair<A, B>(x, y))
                    }
            )
        }
)

fun sat(f: (Char) -> Boolean): (String) -> Pair<Char, String>? =
        bind<Char, Char>(item(), {(x: Char) -> if (f(x)) result<Char>(x) else zero() })

fun char(c: Char) = sat() { it == c }
fun digit() = sat() { it in '0'..'9' }
fun lower() = sat() { it in 'a'..'z' }
fun upper() = sat() { it in 'A'..'Z' }

fun alt<A>(p: (String) -> Pair<A, String>?,
           q: (String) -> Pair<A, String>?) = {(s: String) ->
    val t = p(s)
    if (t != null)
        t
    else
        q(s)
}

fun apply<A, B>(p: (String) -> Pair<A, String>?,
                f: (A) -> B): (String) -> Pair<B, String>? = {(s: String) ->
    val ans = p(s)
    if (ans == null)
        null
    else
        Pair<B, String>(f(ans.first), ans.second)
}

fun letter() = alt(lower(), upper())
fun alphanum() = alt(letter(), digit())

fun nc<A>(p: (String) -> Pair<A, String>?) = {(s: String) ->
    val ans = p(s)
    if (ans == null)
        null
    else
        Pair<A, String>(ans.first, s)
}

fun word(): (String) -> Pair<String, String>? = alt(
        bind<Char, String>(
                letter(),
                {(x: Char) ->
                    bind<String, String>(
                            word(),
                            {(xs: String) -> result<String>(x.toString().concat(xs)) }
                    )
                }
        ),
        result<String>("")
)

fun string(str: String): (String) -> Pair<String, String>? =
        if (str == "")
            result("")
        else
            bind<Char, String>(
                    char(str[0]),
                    {(s0: Char) ->
                        bind<String, String>(
                                string(str.substring(1)),
                                {(s1: String) ->
                                    result(str)
                                }
                        )
                    }
            )

fun many<A>(p: (String) -> Pair<A, String>?): (String) -> Pair<List<A>, String>? = alt(
        bind<A, List<A>>(
                p,
                {(x: A) ->
                    bind<List<A>, List<A>>(
                            many<A>(p),
                            {(xs: List<A>) ->
                                result(x cons xs)
                            }
                    )
                }
        ),
        result(ArrayList<A>())
)

fun many1<A>(p: (String) -> Pair<A, String>?): (String) -> Pair<List<A>, String>? =
        bind<A, List<A>>(
                p,
                {(x: A) ->
                    bind<List<A>, List<A>>(
                            many<A>(p),
                            {(xs: List<A>) ->
                                result(x cons xs)
                            }
                    )
                }
        )


fun digitToInt(): (String) -> Pair<Int, String>? =
        bind<Char, Int>(
                digit(),
                {(x: Char) ->
                    result(x.toInt() - '0'.toInt())
                }
        )

fun nat(): (String) -> Pair<Int, String>? = {(s: String) ->
    val ans = many1(digitToInt())(s)
    if (ans == null)
        null
    else
        Pair<Int, String>(ans.first.foldl({(x: Int, y: Int) -> x * 10 + y }, 0), ans.second)
}

fun int(): (String) -> Pair<Int, String>? = alt(
        bind<Char, Int>(
                char('-'),
                {(x: Char) ->
                    bind<Int, Int>(
                            nat(),
                            {(n: Int) -> result(-n) }
                    )
                }
        ),
        nat()
)

fun chainl1<A>(p: (String) -> Pair<A, String>?,
               op: (String) -> Pair<(A, A) -> A, String>?): (String) -> Pair<A, String>? = {(s: String) ->
    val op2f = seq(op, p)
    val fys = many(op2f)
    bind<A, A>(
            p,
            {(x: A) ->
                bind<List<Pair<(A, A) -> A, A>>, A>(
                        fys,
                        {(xs: List<Pair<(A, A) -> A, A>>) ->
                            result(xs.foldl(
                                    {(x1: A, x2: Pair<(A, A) -> A, A>) -> x2.first(x1, x2.second) },
                                    x
                            ))
                        }
                )
            }
    )(s)
}

// expression parser

fun bracket<A, B, C>(
        open: (String) -> Pair<A, String>?,
        p: (String) -> Pair<B, String>?,
        close: (String) -> Pair<C, String>?): (String) -> Pair<B, String>? =
        bind<A, B>(
                open,
                { bind<B, B>(p, {(ans: B) -> bind<C, B>(close, { result(ans) }) }) }
        )

fun getOp(op: Char) =
        when (op) {
            '+' -> {(x: Int, y: Int) -> x + y }
            '-' -> {(x: Int, y: Int) -> x - y }
            '*' -> {(x: Int, y: Int) -> x * y }
            else -> {(x: Int, y: Int) -> 0 }
        }

fun addop(): (String) -> Pair<((Int, Int) -> Int), String>? = alt(
        apply(char('+'), {(c: Char) -> getOp(c) }),
        apply(char('-'), {(c: Char) -> getOp(c) })
)

fun expr() = chainl1(factor(), addop())

fun factor(): (String) -> Pair<Int, String>? = alt(
        digitToInt(),
        bracket(char('('), {(s: String) -> expr()(s) }, char(')'))
)

*/